import java.util.Arrays;
import java.util.Scanner;

public class Text {
    //二进制1的个数
    public static void main15(String[] args) {
        int a = 8;
        int count = 0;
        while(a != 0){
            a = a & (a-1);
            count++;
        }
        System.out.println(count);
    }
    //求两个数的最大公约数,辗转相除法
    public static void main14(String[] args) {
        int a = 52;
        int b = 18;
        int c = a % b;
        while(c != 0){
            a = b;
            b = c;
            c = a % b;
        }
        System.out.println(b);
    }
    //计算分数的值1/1-1/2+1/3-1/4+...+1/99-1/100
    public static void main13(String[] args) {
        double sum = 0;
        int flg = 1;
        for (int i = 1; i <= 100; i++) {
            sum +=((double)1/i*flg);
            flg *= (-1);
        }
        System.out.println(sum);
    }
    //求出0～n之间的所有“水仙花数”并输出。
    // “水仙花数”是指一个三位数，其各位数字的立方和确好等于该数本身
    // 如；153＝1^3＋5^3＋3^3，则153是一个“水仙花数“。
    public static void main12(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        //计算位数
        for (int i = 0; i <= n; i++) {
            int count = 0;
            int tmp = i;
            while(tmp != 0){
                count++;
                tmp /= 10;
            }
            tmp = i;
            int sum = 0;
            while(tmp != 0){
                sum += Math.pow(tmp % 10,count);
                tmp /= 10;
            }
            if(sum == i){
                System.out.println(i);
            }

        }
    }
    //打印X图形
    public static void main11(String[] args) {
        Scanner scan = new Scanner(System.in);
        while(scan.hasNextInt()){
            int n = scan.nextInt();
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    if(i == j || i + j ==(n-1)){
                        System.out.print("*");
                    }else{
                        System.out.print(" ");
                    }
                }
                System.out.println();
            }
        }
    }
    //判断一个数是否是素数,大于一的自然数除了一和它本身外没有其他因数
    public static void main10(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        boolean flg = true;
        for(int i = 2;i <= Math.sqrt(n);i++) {
          if(n % i == 0){
              flg = false;
          }
        }
        System.out.println(n+(flg?"是素数":"不是素数"));
    }
    //数字9出现的次数
    public static void main9(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int count = 0;
        while(n > 10){
            if(n % 10 == 9){
                count++;
            }
            n/=10;
        }
        if(n == 9){
            count++;
        }
        System.out.println("9出现的次数："+count);
    }
    //汉诺塔问题
    public static void move(char pos1,char pos2){
        System.out.print(pos1+"->"+pos2+" ");
    }
    public static void Hanoi(int n,char pos1,char pos2,char pos3){
        if(n == 1){
            move(pos1,pos3);
        }else{
            Hanoi(n-1,pos1,pos3,pos2);
            move(pos1,pos3);
            Hanoi(n-1,pos2,pos1,pos3);
        }
    }

    public static void main8(String[] args) {
        Hanoi(1,'A','B','C');
        System.out.println();
        Hanoi(2,'A','B','C');
        System.out.println();
        Hanoi(3,'A','B','C');
    }
    //改变原数组的值
    public static int[] transform(int[] array){
        for (int i = 0; i < array.length; i++) {
            array[i] = array[i] * 2;
        }
        return array;
    }

    public static void main7(String[] args) {
        int[] array = {1,2,3};
        int[] arr = transform(array);
        System.out.println(Arrays.toString(arr));
    }

    //方法的重载
    public static int max2(int x, int y) {
        if (x > y) {
            return x;
        } else {
            return y;
        }
    }

    public static int max3(int x, int y, int z) {
        int max = max2(x, y);
        if (max < z) {
            max = z;
        }
        return max;
    }

    public static int sum(int x,int y){
        return x + y;
    }
    public static int sum(int x,int y,int z){
        return x + y + z;
    }

    public static int maxNum(int x,int y){
        if(x > y){
            return x;
        }else{
            return y;
        }
    }
    public static float maxNum(float x,float y,float z) {
        float max = 0;
        if (x > y) {
            max = x;
        }else{
            max = y;
        }
        if (z > max) {
            max = z;
        }
        return max;
    }

    public static void main4(String[] args) {
        int a = 85;
        int b = 61;
        float c = 8.6f;
        float d = 99.2f;
        float e = 55.4f;
        System.out.println(maxNum(a, b));
        System.out.println(maxNum(c, d, e));
    }


    public static void main3(String[] args) {
        int a = 66;
        int b = 22;
        int c = 6;
        System.out.println(sum(a, b));
        System.out.println(sum(a, b, c));
    }

    public static void main2(String[] args) {
        int a = 10;
        int b = 5;
        int c = 64;
        System.out.println(max2(a, c));
        System.out.println(max3(a, b, c));
    }


    //按顺序打印数字的每一位
    public static void printnum(int n){
        if(n>9){
             printnum(n/10);
        }
        System.out.println(n%10);
    }
    //递归求1+2+3+4+5+6+7+8+9+10
    public static int sum(int n){
        if(n==1){
            return 1;
        }
        return n+sum(n-1);
    }
    //数字的每一位之和
    public static int sume(int n){
        if(n < 10){
            return n;
        }
        return sume(n/10)+n % 10;
    }
    //1 1 2 3 5 8 13 21 34....
    public static int fib(int n){
        int f1 = 1;
        int f2 = 1;
        int f3 = 0;
        for(int i = 3;i <= n;i++){
            f3=f1 + f2;
            f1 = f2;
            f2 = f3;
        }
        return f3;
    }

    public static void main6(String[] args) {
        System.out.println(fib(6));
    }
    //打印出数组
    public static void myToString(int[] array){
        System.out.print("[");
        for (int i = 0; i < array.length; i++) {
            System.out.print(array[i]);
            if(i!=array.length-1){
                System.out.print(",");
            }
        }
        System.out.print("]");
    }
    //冒泡排序（优化）
    public static void bubble(int[] array){
        for (int i = 0; i < array.length - 1; i++) {
            boolean flg = false;
            for (int j = 0; j < array.length-1-i; j++) {
                if(array[j]>array[j+1]){
                    int tmp = array[j];
                    array[j] = array[j+1];
                    array[j+1] = tmp;
                    flg = true;
                }
            }
            if(flg == false){
                return;
            }
        }
    }
    public static void main1(String[] args) {
        printnum(156);
        System.out.println("==========");
        int n = sum(5);
        System.out.println(n);
        int a = sume(123);
        System.out.println(a);
        System.out.println(fib(5));
        System.out.println("==========");
        //数组
        int[] array = {1,2,3,4,5};
        int[] array2 = new int[]{1,2,3};
        int[] array3 = new int[5];
        System.out.println(array[3]);
        for (int i = 0; i < array.length; i++) {
            System.out.println(array[i]);
        }
        System.out.println("==========");
        myToString(array2);
        int[] ary = {5,99,64,81,6,25,10};
        System.out.println();
        System.out.println("排序前："+ Arrays.toString(ary));
        bubble(ary);
        System.out.println("排序后："+Arrays.toString(ary));
    }
}
